import java.util.Deque;
import java.util.LinkedList;

/**
* @description: 919. 完全二叉树插入器
* @author hewei
* @date 2022/7/25 14:07
* @version 1.0
*/

public class CBTInserter {

    Deque<TreeNode> queue;
    TreeNode root;
    public CBTInserter(TreeNode root) {
        this.root = root;
        queue = new LinkedList<>();
        queue.addLast(root);
    }

    public int insert(int val) {
        while (!queue.isEmpty() && queue.peekFirst().left != null & queue.peekFirst().right != null) {
            TreeNode node = queue.pollFirst();
            queue.addLast(node.left);
            queue.addLast(node.right);
        }
        TreeNode node = new TreeNode(val);
        TreeNode peek = queue.peekFirst();
        if (peek.left == null) {
            peek.left = node;
        } else peek.right = node;
        return peek.val;
    }

    public TreeNode get_root() {
        return root;
    }
}
